#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<unordered_set>

using namespace std;

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> us;
    for (auto it : wordDict) us.insert(it);

    int n = s.size();
    vector<int> f(n + 1);
    f[0] = true;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (f[j] && us.find(s.substr(j, i - j)) != us.end())
            {
                f[i] = true;
                break;
            }
        }
    }
    return f[n];
}